1. Field of the Invention
The present invention generally relates to redundant array of independent disks (RAID) systems and more specifically to a RAID-6 computation system and method.
2. Description of the Related Art
Certain storage systems require total storage capacity and overall performance beyond that of one independent disk drive, for a given generation of disk drive technology. These storage systems typically organize a plurality of independent disk drives into a parallel array of disk drives, wherein multiple blocks of data may be accessed simultaneously by accessing the multiple disk drives in parallel. While a parallel array of disk drives provides increased storage capacity and generally increased performance, the mean time to failure (MTTF) of the array degrades proportionately with an increasing number of independent disk drives. For example, if a single disk drive has an MTTF of F and an array of disks includes N disks, then the MTTF of the array is approximately F/N. To protect data stored on the array of disks from a degraded MTTF, fault recovery mechanisms are typically employed. A redundant array of independent disks (RAID) array refers to a set of well known techniques for organizing data storage in a disk array of substantially identical disk drives that can provide fault recovery and improve overall MTTF of the disk array.
One RAID organization known in the art is “RAID-6,” in which N participating disk drives in a disk array can store an equivalent capacity of N−2 disk drives of user data. An equivalent capacity of two disk drives of related error recovery data (“erasure code” data) provides fault protection for the N disk drives. One property of conventional RAID-6 is that two additional independent disk drives of storage can protect up to 255 equivalently sized disk drives of user data. Another property of conventional RAID-6 is that up to two disk drives may simultaneously fail without loss of data in the disk array. One assumption is that the RAID-6 system can identify each failed disk drive.
Data in a RAID-6 disk array of N disk drives is organized as a plurality of stripes that each includes N sectors. Each stripe includes one sector per disk drive, and the sectors of a given stripe share a common sector offset value within a respective disk drive. For a given stripe, N−2 sectors store user data and two sectors store fault recovery data, known as “erasure code bytes,” which may be used to protect associated user data in the stripe. Two types of erasure code bytes, referred to as “P code bytes” and “Q code bytes,” are stored within the two sectors of fault recovery data. The P code bytes are computed as an exclusive-OR sum of N−2 bytes of user data sharing an identical byte offset within each of N−2 sectors in a given stripe. Hence, each disk drive contributes one byte to a P code byte of a corresponding byte offset. A corresponding Q code byte is computed from the same set of N−2 bytes of user data. The Q code byte is computed as an exclusive-OR sum of N−2 terms, where each term is computed by multiplying a corresponding byte of user data by a coefficient that is a function of sector number and drive position in the disk array, wherein the multiplication operation is performed in a Galois Field GF(2^8) as an extension field over GF(2).
Persons skilled in the art will recognize that with one P code byte, one Q code byte, and N−2 bytes of user data in a stripe, any two bytes from the N byte stripe may be lost (erased) and the N−2 bytes of user data may be, nonetheless, recovered. As a result, any two disk drives within a RAID-6 array may fail, causing the RAID-6 array to operate in a compromised mode, but a without loss of user data. Furthermore, replacement drives may be installed within the RAID-6 array and populated with recovered data during a recovery mode.
While a RAID-6 disk array can continue to operate in a compromised or recovery mode without loss of user data, the associated computational load needed to continue operating may become a significant burden for a host processor. In certain practical RAID-6 scenarios, forward progress of user applications accessing a compromised RAID-6 array can be almost completely stymied by complex RAID-6 computations needed to access to the compromised array.
Accordingly, what is needed in the art is a technique that enables more efficient RAID-6 computations.